package com.ruijixiang.leetcode.everyday.leetcode2024.leetcode202412;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class leetcode20241222 {
    // 将整数按权重排序
    // 冰雹猜想，记忆化搜索

    private static final Map<Integer,Integer> memo=new HashMap<>();

    public int getKth(int lo,int hi,int k){
        Integer[] nums=new Integer[hi-lo+1];
        Arrays.setAll(nums,i->i+lo);// 初始化值
        Arrays.sort(nums,(x,y)->{
            int fx=dfs(x),fy=dfs(y);
            return fx!=fy ? fx-fy : x-y;
        });
        return nums[k-1];
    }

    private int dfs(int i){
        if(i==1){
            return 0;
        }
        if(memo.containsKey(i)){// 之前计算过
            return memo.get(i);
        }
        if(i%2==1){// 奇数
            memo.put(i,dfs((i*3+1)/2)+2);
        }else{
            memo.put(i,dfs(i/2)+1);
        }
        return memo.get(i);
    }
}
